//
//  CacheLookup.h
//  面试题
//
//  Created by Toj on 8/15/21.
//

buckets: hash表

NORMAL, _objc_msgSend, __objc_msgSend_uncached
消息缓存查找 汇编底层实现:
{
.macro CacheLookup
    // x1 = SEL, x16 = isa
    ldp    x10, x11, [x16, #CACHE]    // x10 = buckets, x11 = occupied|mask
    and    w12, w1, w11        // x12 = _cmd & mask
    add    x12, x10, x12, LSL #4    // x12 = buckets + ((_cmd & mask)<<4)

    ldp    x9, x17, [x12]        // {x9, x17} = *bucket
1:    cmp    x9, x1            // if (bucket->sel != _cmd)
    b.ne    2f            //     scan more
    CacheHit $0            // call or return imp
    
2:    // not hit: x12 = not-hit bucket
    CheckMiss $0            // miss if bucket->sel == 0
    cmp    x12, x10        // wrap if bucket == buckets
    b.eq    3f
    ldp    x9, x17, [x12, #-16]!    // {x9, x17} = *--bucket
    b    1b            // loop

3:    // wrap: x12 = first bucket, w11 = mask
    add    x12, x12, w11, UXTW #4    // x12 = buckets+(mask<<4)

    // Clone scanning loop to miss instead of hang when cache is corrupt.
    // The slow path may detect any corruption and halt later.

    ldp    x9, x17, [x12]        // {x9, x17} = *bucket
1:    cmp    x9, x1            // if (bucket->sel != _cmd)
    b.ne    2f            //     scan more
    // 找到实现
    CacheHit $0            // call or return imp
    
2:    // not hit: x12 = not-hit bucket
    // 没有找到实现
    CheckMiss $0            // miss if bucket->sel == 0
    cmp    x12, x10        // wrap if bucket == buckets
    b.eq    3f
    ldp    x9, x17, [x12, #-16]!    // {x9, x17} = *--bucket
    b    1b            // loop

3:    // double wrap
    JumpMiss $0
    
.endmacro
}

// CacheHit: 找的IMP的跳转
{
    .macro CacheHit
    .if $0 == NORMAL
        MESSENGER_END_FAST
        // 直接调用
        br    x17            // call imp
    .elseif $0 == GETIMP
        mov    x0, x17            // return imp
        ret
    .elseif $0 == LOOKUP
        ret                // return imp via x17
    .else
    .abort oops
    .endif
    .endmacro
}

// JumpMiss: 找不到IMP的跳转
{
    .macro JumpMiss
    .if $0 == GETIMP
        b    LGetImpMiss
    .elseif $0 == NORMAL
        // 跳转 __objc_msgSend_uncached 带缓冲不带缓存的IMP地址
        b    __objc_msgSend_uncached
    .elseif $0 == LOOKUP
        b    __objc_msgLookup_uncached
    .else
    .abort oops
    .endif
    .endmacro
}

// __objc_msgSend_uncached
{
    STATIC_ENTRY __objc_msgSend_uncached
    UNWIND __objc_msgSend_uncached, FrameWithNoSaves

    // THIS IS NOT A CALLABLE C FUNCTION
    // Out-of-band x16 is the class to search
    
    MethodTableLookup
    br    x17

    END_ENTRY __objc_msgSend_uncached
}

// MethodTableLookup
{
    .macro MethodTableLookup
        
        // push frame
        stp    fp, lr, [sp, #-16]!
        mov    fp, sp

        // save parameter registers: x0..x8, q0..q7
        sub    sp, sp, #(10*8 + 8*16)
        stp    q0, q1, [sp, #(0*16)]
        stp    q2, q3, [sp, #(2*16)]
        stp    q4, q5, [sp, #(4*16)]
        stp    q6, q7, [sp, #(6*16)]
        stp    x0, x1, [sp, #(8*16+0*8)]
        stp    x2, x3, [sp, #(8*16+2*8)]
        stp    x4, x5, [sp, #(8*16+4*8)]
        stp    x6, x7, [sp, #(8*16+6*8)]
        str    x8,     [sp, #(8*16+8*8)]

        // receiver and selector already in x0 and x1
        mov    x2, x16
        // 跳转 _class_lookupMethodAndLoadCache3
        bl    __class_lookupMethodAndLoadCache3

        // imp in x0
        mov    x17, x0
        
        // restore registers and return
        ldp    q0, q1, [sp, #(0*16)]
        ldp    q2, q3, [sp, #(2*16)]
        ldp    q4, q5, [sp, #(4*16)]
        ldp    q6, q7, [sp, #(6*16)]
        ldp    x0, x1, [sp, #(8*16+0*8)]
        ldp    x2, x3, [sp, #(8*16+2*8)]
        ldp    x4, x5, [sp, #(8*16+4*8)]
        ldp    x6, x7, [sp, #(8*16+6*8)]
        ldr    x8,     [sp, #(8*16+8*8)]

        mov    sp, fp
        ldp    fp, lr, [sp], #16

    .endmacro
}
